#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct BSTREE BST;
struct BSTREE{
	ElementType Data;
	BST *Left;
	BST *Right;
};

BST *Insert(BST*,ElementType);
BST *Find(BST*,ElementType);
BST *FindMax(BST*);
BST *FindMin(BST*);
BST *Delete(BST*,ElementType);
void PreOrder(BST *);

int main(void){
	BST *root=NULL;
	int data=0;
	scanf("%d",&data);
	while( -1 != data ){
		printf("Insert %3d\n",data);
		root=Insert(root,data);
		PreOrder(root);
		printf("\n");
		scanf("%d",&data);
	}
	scanf("%d",&data);
	while( -1 != data ){
		printf("Delete %3d\n",data);
		if( Find(root,data) ){
			root=Delete(root,data);
			PreOrder(root);
			printf("\n");
		}
		scanf("%d",&data);
	}
	printf("Max %d",FindMax(root)->Data);
	printf("Min %d",FindMin(root)->Data);
	return 0;
}
BST *FindMax(BST *root){
	if( root )
		while( root->Right )
			root=root->Right;
	return root;
}

BST *FindMin(BST *root){
	if( root )
		while( root->Left )
			root=root->Left;
	return root;
}
BST *Find(BST* root,ElementType x){
	while( root ){
		if( x < root->Data )
			root=root->Left;
		else if( x > root->Data )
			root=root->Right;	
		else{	// x == root->Data
			break;
		}
	}
	return root;
}
BST *Insert(BST *root,ElementType x){
	BST *new=malloc(sizeof(BST));
	new->Data=x;
	new->Left=new->Right=NULL;
	BST **ptr=&root;
	while ( *ptr ){
		if( x < (*ptr)->Data )
			ptr=&((*ptr)->Left);
		else if( x > (*ptr)->Data )
			ptr=&((*ptr)->Right);
		else{
			free(new);
			return root;
		}
	}
	(*ptr)=new;
	return root;
}

BST *Delete(BST *root,ElementType x){
	if( !root )return root;
	if( x < root->Data )
		root->Left=Delete(root->Left,x);
	else if( x > root->Data )
		root->Right=Delete(root->Right,x);
	else{	//	x == root->Data		return Delete(
		if( root->Left && root->Right ){
			BST *tmp=FindMin(root->Right);
			root->Data=tmp->Data;
			root->Right=Delete(root->Right,tmp->Data);
		}else{
			BST *tmp=root;
			if( !root->Left )
				root=root->Right;
			else
				root=root->Left;
			free(tmp);
		}
	}
	return root;
}
void PreOrder(BST *root){
	if( root ){
		printf("%4d",root->Data);
		PreOrder(root->Left);
		PreOrder(root->Right);
	}
	return;
}
